package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Arrays;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-28 17:39
 */
public class BE740删除并获得点数 {


    public static void main(String[] args) {

        int[] nums = {1, 1, 1, 2, 4, 5, 5, 5, 6};

        System.out.println(deleteAndEarn(nums));
    }


    /**
     * 1.排序
     * 2.将所有的相同数字合并(遍历过程中合并)成一个数字 相邻的数字不能取 xxx
     * 不能合并  此问题不能完全等价于打家劫舍  因为数字不一定相邻
     *
     * 3.优化----使用一个数据存储合并后的值 坐标为原值 坐标对应的数值为个数
     *
     * @param nums
     * @return
     */
    public static int deleteAndEarn(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        //1.排序
        Arrays.sort(nums);

        int totalOne = getNumCount(nums[0], 0, nums);
        int one = nums[0] * totalOne;
        if (totalOne == nums.length) {
            return one;
        }
        int totalTwo = getNumCount(nums[totalOne], totalOne, nums);
        int two;
        if (nums[totalOne] - nums[0] == 1) {
            two = Math.max(nums[totalOne] * totalTwo, one);
        } else {
            two = nums[totalOne] * totalTwo + one;
        }
        int nextNum = nums[totalOne];
        int total = totalOne + totalTwo;
        for (int i = total; i < nums.length; i++) {
            totalTwo = getNumCount(nums[i], i, nums);
            int next;
            if (nums[i] - nextNum == 1) {
                next = Math.max(one + totalTwo * nums[i], two);
            } else {
                next = two + totalTwo * nums[i];
            }
            nextNum = nums[i];
            one = two;
            two = next;
            i += totalTwo-1;
        }
        return two;
    }

    //获取指定坐标值总个数
    public static int getNumCount(int num, int i, int[] nums) {
        int total = 1;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == num) {
                total++;
            } else {
                return total;
            }
        }
        return total;
    }
}
